package leetcode_周赛._2023._01;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 327 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/1/8 20:29
 */
public class _08 {

    /**
     * 正整数和负整数的最大计数
     * 算法：二分查找
     */
    public int maximumCount(int[] nums) {
        return Math.max(binarySearch(nums, 0), nums.length - binarySearch(nums, 1));
    }

    int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    /**
     * 执行 K 次操作后的最大分数
     * 算法：堆
     */
    public long maxKelements(int[] nums, int k) {
        long ans = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) queue.offer(num);
        while (k-- > 0) {
            Integer max = queue.poll();
            ans += max;
            max = (max + 2) / 3;
            queue.offer(max);
        }
        return ans;
    }

    /**
     * 使字符串总不同字符的数目相等
     * 算法：模拟
     * 分别计算出两个字符串中字符的数量
     * 枚举两个字符串中字符交换的情况
     */
    public boolean isItPossible(String word1, String word2) {
        Map<Character, Integer> c1 = new HashMap<>(), c2 = new HashMap<>();
        for (int i = 0; i < word1.length(); i++) {
            char c = word1.charAt(i);
            c1.put(c, c1.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < word2.length(); i++) {
            char c = word2.charAt(i);
            c2.put(c, c2.getOrDefault(c, 0) + 1);
        }
        int t1 = c1.size(), t2 = c2.size();
        for (Map.Entry<Character, Integer> entry1 : c1.entrySet()) {
            char x = entry1.getKey();
            boolean flag = entry1.getValue() == 1;
            for (Map.Entry<Character, Integer> entry2 : c2.entrySet()) {
                char y = entry2.getKey();
                // 分情况讨论：x == y or x != y
                // 如果要交换的字符不相等, 那么交换之后两个字符串的不同数量可能会变
                int l1 = t1, l2 = t2;
                if (x != y) {
                    if (flag) --l1;
                    if (!c1.containsKey(y)) ++l1;
                    if (entry2.getValue() == 1) --l2;
                    if (!c2.containsKey(x)) ++l2;
                }
                if (l1 == l2) return true;
            }
        }
        return false;
    }

}
